package BinaryTree;

import java.util.HashMap;
import java.util.Map;
/*
* 从前序和中序遍历序列中构造二叉树
* 通过前序序列,找到中序遍历的根节点位置.左右分辨递归
* 递归的六个参数:
*   左: 前序遍历与后序遍历的序列数组
*       前序遍历的左子树边界,中序遍历的左子树边界
*  右: 同理
*
* */
public class BuildTree {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       int n=inorder.length;
        for(int i=0;i<n;i++){
            map.put(inorder[i],i);
        }
        int root = map.get(preorder[0]);
        return myBuild(preorder,inorder,0,n-1,0,n-1);
    }

    TreeNode myBuild(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if(preorder_left>preorder_right){
            return null;
        }
        int inorder_root = map.get(preorder[preorder_left]);
        int size_left_subtree=inorder_root-inorder_left;
        TreeNode root = new TreeNode(preorder[preorder_left]);
        root.left=myBuild(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,
                inorder_left,inorder_root-1);
        root.right=myBuild(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,
                inorder_root+1,inorder_right);
        return root;
    }
}
